const { createBiTree,createBitreeByLevelOrder } =  require("./createBitree");

const biTree = createBiTree(10);

/**
 * 
 * @param {biTree} root 
 * @description  
 */
function postOrderByRecursion(root) {
    if(root === null) {
        return ;
    }
    postOrderByRecursion(root.left);
    postOrderByRecursion(root.right);
    console.log(root.value);

}

/**
 * 
 * @param {biTree} root 
 * @难点 递归遍历的重点是要判断递归时是从左孩子还是从右孩子回溯的
 *              （借助一个临时指针指向上一次访问的节点，然后和当前节点的右孩子节点作比较）
 * @算法概述 整个程序的递归逻辑：
 *           深入阶段：首先不断向左分支深入,遇到 null 时读取栈顶元素,
 *           判断和回溯阶段：对右子树进行判断(是否为null,是否已经遍历过了),然后决定是 向右子树深入 还是 弹出出栈顶元素并遍历(回溯阶段)
 *                         重点在于遍历元素后要使用一个变量保存遍历了的元素，并且要将指向当前节点的变量置为null, (pre=temp,temp=null)以让程序进入判断环节
 */
function postOrderByNoRecursion(root) {

    const stack = [];
    let temp = root;
    let pre = null; // pre 指向前一次读取过内容的节点

    while(temp !== null || stack.length !== 0) {

        if(temp !== null) { // 递归深入阶段
            stack.push(temp);
            temp = temp.left;
        }else { 
            temp = stack.slice(-1)[0];
            if(temp.right !== null && pre !== temp.right) { // 向右分支深入

                temp = temp.right;
            } else { // 递归归并阶段

                temp = stack.pop();
                console.log(temp.value);
                pre = temp; // 重点
                temp = null; // 重点

            }
        }
    }
}

postOrderByRecursion(biTree);
console.log('====================');
postOrderByNoRecursion(biTree);